package SubjectString;

public class StrStr {

/**
 * 难度：中等
 * 
 * 28. 实现 strStr()
 * 	实现 strStr() 函数。
 * 	给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找
 * 	出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 * 
 * 示例 1:
 * 	输入: haystack = "hello", needle = "ll"
 * 	输出: 2
 * 
 * 示例 2:
 * 	输入: haystack = "aaaaa", needle = "bba"
 * 	输出: -1
 * 
 * 说明:
 * 	当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * 	对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 * 
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		StrStr ss = new StrStr();
		System.out.println(ss.strStr("mississippi","pi"));
	}
	public int strStr(String haystack, String needle) {
		if(needle.equals(""))return 0;
		int n=0;
		int index=0;
		for(int i=0;i<haystack.length();i++) {
			if(haystack.charAt(i)==needle.charAt(0)&&n==0) {
				n++;
				index=i;
			}else if(haystack.charAt(i)==needle.charAt(n)){
				n++;
			}else {
				if(n!=0)i=index;
				n=0;
				index=0;
			}
			if(n>=needle.length()) {
				return index;
			}
		}
	    return -1;
	}
	//方法一：子串逐一比较 - 线性时间复杂度
	public int strStr1(String haystack, String needle) {
		if(needle.equals(""))return 0;
		int L = needle.length(), n = haystack.length();
		for (int start = 0; start < n - L + 1; ++start) {
			if (haystack.substring(start, start + L).equals(needle)) {
				return start;
			}
	    }
	    return -1;
	}
	//方法二：双指针 - 线性时间复杂度
	public int strStr2(String haystack, String needle) {
		int L = needle.length(), n = haystack.length();
		if (L == 0) return 0;
		int pn = 0;
	    while (pn < n - L + 1) {
	    	// find the position of the first needle character
	    	// in the haystack string
	    	while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn;
	    	// compute the max match string
	    	int currLen = 0, pL = 0;
	    	while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
	    		++pn;
	    		++pL;
	    		++currLen;
	    	}
	    	// if the whole needle string is found,
	    	// return its start position
	    	if (currLen == L) return pn - L;

	    	// otherwise, backtrack
	    	pn = pn - currLen + 1;
	    }
	    return -1;
	}
}
